ff1588d761d55f48f61a52249e1dcc24

<!DOCTYPE html>

<title>Hamiltonkreisproblem</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Hamiltonkreisproblem</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Ein Hamiltonkreis ist ein geschlossener <a href="Weg_(Graphentheorie)" title="Weg (Graphentheorie)">Pfad</a> in einem <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graphen</a>, der jeden <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> genau einmal enthält. Die Frage, ob ein solcher Kreis in einem gegebenen Graphen existiert, ist ein wichtiges Problem der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a>. Im Gegensatz zum leicht lösbaren <a href="Eulerkreisproblem" title="Eulerkreisproblem">Eulerkreisproblem</a>, bei dem ein Kreis gesucht wird, der alle <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a> genau einmal durchläuft, ist das Hamiltonkreisproblem <a href="NP-Vollst%C3%A4ndigkeit" title="NP-Vollständigkeit">NP-vollständig</a>.

Man unterscheidet das Gerichtete Hamiltonkreisproblem in gerichteten Graphen und das Ungerichtete Hamiltonkreisproblem in ungerichteten Graphen. Eine Verallgemeinerung des Hamiltonkreisproblems ist das <a href="Problem_des_Handlungsreisenden" title="Problem des Handlungsreisenden">Problem des Handlungsreisenden</a>, bei dem nach einem kürzesten Hamiltonkreis in einem Graphen mit Kantengewichten gefragt wird.

<div class="mw-heading mw-heading2"><h2 id="Geschichte">Geschichte</h2></div>

Namensgeber des Problems ist der irische <a href="Astronom" title="Astronom">Astronom</a> und <a href="Mathematiker" title="Mathematiker">Mathematiker</a> <a href="Sir_William_Rowan_Hamilton" class="mw-redirect" title="Sir William Rowan Hamilton">Sir William Rowan Hamilton</a>, der 1857 das Spiel „The <a href="Icosian_Game" title="Icosian Game">Icosian Game</a>“ erfand (und später verbesserte zum „Traveller's Dodecahedron or A Voyage Round The World“).

Der „Traveller's Dodecahedron“ besteht aus einem hölzernen, regulären <a href="Dodekaeder" title="Dodekaeder">Dodekaeder</a>, wobei die 20 Knoten mit Namen bekannter Städte assoziiert sind. Ziel ist es, eine Reiseroute entlang der <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a> des Dodekaeders zu finden, die jede Stadt genau einmal besucht und dort aufhört, wo sie beginnt.

Zunächst erscheint die Aufgabenstellung ähnlich dem 1736 von <a href="Leonhard_Euler" title="Leonhard Euler">Leonhard Euler</a> (verneinend) gelösten <a href="K%C3%B6nigsberger_Br%C3%BCckenproblem" title="Königsberger Brückenproblem">Königsberger Brückenproblem</a>, einem Spezialfall des <a href="Eulerkreisproblem" title="Eulerkreisproblem">Eulerkreisproblems</a> und Grundsteinlegung der Graphentheorie. Während für das Eulerkreisproblem aber besonders effiziente Lösungs-Algorithmen existieren, ist bekannt, dass beide Varianten des Hamiltonkreisproblems besonders schwer algorithmisch lösbare Probleme sind. Sowohl die gerichtete als auch die ungerichtete Variante des Hamiltonkreisproblems gehört zur Liste der <a href="Karps_21_NP-vollst%C3%A4ndige_Probleme" title="Karps 21 NP-vollständige Probleme">21 klassischen NP-vollständigen Probleme</a>, für die <a href="Richard_M._Karp" title="Richard M. Karp">Richard M. Karp</a> 1972 in seinem berühmten Artikel die Zugehörigkeit zu dieser Klasse von Problemen nachgewiesen hat.

<div class="mw-heading mw-heading2"><h2 id="Definitionen">Definitionen</h2></div>

Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy"> ein Graph mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |V|=n}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |V|=n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/abe9d03f56a9b67c09250c8725944556f8826299.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.574ex; height:2.843ex;" alt="{\displaystyle |V|=n}" loading="lazy"> <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> (oder Ecken) und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |E|=m}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |E|=m}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b0a6871050174a4c2f5a9df84c785342fa847fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.208ex; height:2.843ex;" alt="{\displaystyle |E|=m}" loading="lazy"> <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a>.

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> heißt hamiltonsch, wenn er einen Hamiltonkreis zulässt, d. h., wenn es einen <a href="Kreis_(Graphentheorie)" class="mw-redirect" title="Kreis (Graphentheorie)">Kreis</a> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> gibt, der alle Knoten aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> enthält. Ein Hamiltonpfad ist ein <a href="Weg_(Graphentheorie)" title="Weg (Graphentheorie)">Pfad</a> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy">, der alle Knoten aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> enthält. Hat <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> einen Hamiltonpfad, so heißt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> semihamiltonsch. (Offensichtlich ist jeder hamiltonsche Graph auch semihamiltonsch.)

Zur Potenz eines Graphen: Für einen Graphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d\in \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d\in \mathbb {N} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6a86f7fcd041c0196f44e7c04f4b3eac94e5a757.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.735ex; height:2.176ex;" alt="{\displaystyle d\in \mathbb {N} }" loading="lazy"> bezeichnet <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G^{d}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G^{d}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/609bc89f4f9b01f87f555dee8023175b9355cc7d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.919ex; height:2.676ex;" alt="{\displaystyle G^{d}}" loading="lazy"> den Graphen auf <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy">, bei dem zwei Knoten genau dann <a href="Nachbarschaft_(Graphentheorie)" title="Nachbarschaft (Graphentheorie)">benachbart</a> sind, wenn sie in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> einen <a href="Abstand_(Graphentheorie)" class="mw-redirect" title="Abstand (Graphentheorie)">Abstand</a> kleiner gleich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> haben. Offenbar gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=G^{1}\subseteq G^{2}\subseteq G^{3}\subseteq \ldots }">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=G^{1}\subseteq G^{2}\subseteq G^{3}\subseteq \ldots }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e542550f9a9d2e397bcafb72abd207ba745ad2ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:25.587ex; height:2.843ex;" alt="{\displaystyle G=G^{1}\subseteq G^{2}\subseteq G^{3}\subseteq \ldots }" loading="lazy">.

Ein beliebiges Tupel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a_{1},\dotsc ,a_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a_{1},\dotsc ,a_{n})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8a2a623d2e6322e07d9afd0b5cf2566ee55722c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.72ex; height:2.843ex;" alt="{\displaystyle (a_{1},\dotsc ,a_{n})}" loading="lazy"> <a href="Nat%C3%BCrliche_Zahl" title="Natürliche Zahl">natürlicher Zahlen</a> heißt hamiltonsch, wenn jeder Graph mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Knoten und punktweise größerer <a href="Gradsequenz" class="mw-redirect" title="Gradsequenz">Gradsequenz</a> hamiltonsch ist. Eine Gradsequenz <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (d_{1},\dotsc ,d_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (d_{1},\dotsc ,d_{n})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8389759f758f1e595fc6e4af997e2744345d684f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.678ex; height:2.843ex;" alt="{\displaystyle (d_{1},\dotsc ,d_{n})}" loading="lazy"> heißt dabei punktweise größer als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a_{1},\dotsc ,a_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a_{1},\dotsc ,a_{n})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8a2a623d2e6322e07d9afd0b5cf2566ee55722c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.72ex; height:2.843ex;" alt="{\displaystyle (a_{1},\dotsc ,a_{n})}" loading="lazy">, wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{i}\geq a_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{i}\geq a_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/97c92090e3419e7c298f29c1a3601460ca915eed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.137ex; height:2.509ex;" alt="{\displaystyle d_{i}\geq a_{i}}" loading="lazy"> gilt für alle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">.

Ein Graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> heißt hypohamiltonsch, wenn er keinen hamiltonschen Kreis besitzt, aber zu jedem seiner Knoten ein Kreis existiert, der alle anderen Knoten enthält.

Der Hamiltonabschluss eines Graphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> ist der <a href="Teilgraph" title="Teilgraph">Obergraph</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> mit identischer Knotenmenge und zusätzlich <a href="Iteration" title="Iteration">iterativ</a> eingefügten Kanten, die nichtadjazente Knoten mit Gradsumme größer gleich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> miteinander verbinden, solange dies möglich ist. Der Hamiltonabschluss eines Graphen ist eindeutig.

<div class="mw-heading mw-heading2"><h2 id="Eigenschaften">Eigenschaften</h2></div>

Jeder Hamiltonkreis kann durch Entfernen einer seiner <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a> in einen Hamiltonweg umgewandelt werden. Ein Hamiltonweg kann jedoch nur dann zu einem Hamiltonkreis erweitert werden, wenn seine Endknoten benachbart sind.

Alle hamiltonschen Graphen sind 2-<a href="Zusammenh%C3%A4ngender_Graph" class="mw-redirect" title="Zusammenhängender Graph">zusammenhängend</a>, aber ein 2-zusammenhängender Graph muss nicht hamiltonsch sein, zum Beispiel der <a href="Petersen-Graph" title="Petersen-Graph">Petersen-Graph</a>.

Ein <a href="Eulerscher_Graph" class="mw-redirect" title="Eulerscher Graph">eulerscher Graph</a>, also ein <a href="Zusammenh%C3%A4ngender_Graph" class="mw-redirect" title="Zusammenhängender Graph">zusammenhängender Graph</a>, in dem jeder <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> einen geraden <a href="Grad_(Graphentheorie)" title="Grad (Graphentheorie)">Grad</a> hat, besitzt notwendigerweise einen Eulerkreis, wobei der geschlossene Weg genau einmal durch jede <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kante</a> verläuft. Dieser <a href="Weg_(Graphentheorie)" title="Weg (Graphentheorie)">Weg</a> entspricht einem Hamiltonkreis im zugehörigen <a href="Kantengraph" title="Kantengraph">Kantengraphen</a>, sodass der Kantengraph jedes eulerschen Graphen ein hamiltonscher Graph ist. Kantengraphen können andere Hamiltonkreise haben, die nicht den Eulerkreisen entsprechen, und insbesondere ist der Kantengraph jedes hamiltonschen Graphen selbst hamiltonsch, unabhängig davon, ob der Graph ein eulerscher Graph ist.

Ein <a href="Turniergraph" title="Turniergraph">Turniergraph</a> mit mehr als zwei <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> ist genau dann ein hamiltonscher Graph, wenn er <a href="Stark_zusammenh%C3%A4ngend" class="mw-redirect" title="Stark zusammenhängend">stark zusammenhängend</a> ist.

Die Anzahl der verschiedenen Hamiltonkreise in einem <a href="Vollst%C3%A4ndiger_Graph" title="Vollständiger Graph">vollständigen</a> <a href="Ungerichteter_Graph" class="mw-redirect" title="Ungerichteter Graph">ungerichteten Graphen</a> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> beträgt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {1}{2}}\cdot (n-1)!}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {1}{2}}\cdot (n-1)!}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a3b26488b9f3889aa9c79dda588dd8a8c4e4ebb6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:11.191ex; height:3.509ex;" alt="{\displaystyle {\tfrac {1}{2}}\cdot (n-1)!}" loading="lazy"> und in einem vollständigen <a href="Gerichteter_Graph" title="Gerichteter Graph">gerichteten Graphen</a> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Knoten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n-1)!}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n-1)!}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7eb71a5f562b97650728f30493f43e96c15b4287.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.854ex; height:2.843ex;" alt="{\displaystyle (n-1)!}" loading="lazy">. Dabei werden Hamiltonkreise, die bis auf ihren Startknoten gleich sind, nicht mehrfach gezählt.

<div class="mw-heading mw-heading2"><h2 id="Sätze_über_Hamiltonkreise">Sätze über Hamiltonkreise</h2></div>

Welche Bedingungen an einen Graphen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\geq 3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\geq 3}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/73136e4a27fe39c123d16a7808e76d3162ce42bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.656ex; height:2.343ex;" alt="{\displaystyle n\geq 3}" loading="lazy"> haben die Existenz eines Hamiltonkreises zur Folge? Besonders wichtige Theoreme sind folgend chronologisch aufgelistet.

<div class="mw-heading mw-heading3"><h3 id="Sätze">Sätze</h3></div>

<ul><li><a href="Gabriel_Andrew_Dirac" title="Gabriel Andrew Dirac">G. A. Dirac</a> (1952), der historische Ausgangspunkt der Entdeckung einer ganzen Reihe von Bedingungen: Jeder <a href="Einfacher_Graph" title="Einfacher Graph">einfache Graph</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> mit <a href="Minimalgrad" class="mw-redirect" title="Minimalgrad">Minimalgrad</a> mindestens <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {n}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {n}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c2fd493036e5cdcb87f9ddfdc7ab475e74636b5e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:1.822ex; height:3.176ex;" alt="{\displaystyle {\tfrac {n}{2}}}" loading="lazy"> hat einen Hamiltonkreis.<a href="#cite_note-SachsI-1">[1]</a></li></ul>

<ul><li><a href="William_T._Tutte" class="mw-redirect" title="William T. Tutte">W. T. Tutte</a> (1956): Jeder <a href="K-Zusammenhang" title="K-Zusammenhang">4-zusammenhängende</a> <a href="Planarer_Graph" title="Planarer Graph">planare Graph</a> hat einen Hamiltonkreis.</li></ul>

<ul><li><a href="%C3%98ystein_Ore" title="Øystein Ore">Ø. Ore</a> (1960): Ist die Summe der Grade je zweier nicht-adjazenter Knoten eines einfachen Graphen mindestens <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, so ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> hamiltonsch.<a href="#cite_note-SachsI-1">[1]</a></li></ul>

<ul><li><a href="Lajos_P%C3%B3sa" title="Lajos Pósa">L. Pósa</a> (1962) mit einer Verallgemeinerung früherer Ergebnisse von G. A. Dirac und Ø. Ore: Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> ein <a href="Einfacher_Graph" title="Einfacher Graph">einfacher Graph</a> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\geq 3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\geq 3}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/73136e4a27fe39c123d16a7808e76d3162ce42bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.656ex; height:2.343ex;" alt="{\displaystyle n\geq 3}" loading="lazy"> <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a>. Es gelte außerdem für alle natürlichen Zahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k<{\tfrac {n-1}{2}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k<{\tfrac {n-1}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6dc5a76b6bdc52c535a0e1cda6c5791fad0cb051.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:8.233ex; height:3.676ex;" alt="{\displaystyle k<{\tfrac {n-1}{2}}}" loading="lazy">, dass die Anzahl der Knoten mit <a href="Grad_(Graphentheorie)" title="Grad (Graphentheorie)">Grad</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\leq k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\leq k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dd9bac8e1f48226c218bbc2331425ee20084b822.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.437ex; height:2.343ex;" alt="{\displaystyle v\leq k}" loading="lazy"> kleiner als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> ist. Falls <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> ungerade ist, sei die Anzahl aller Knoten mit Grad <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\leq {\tfrac {n-1}{2}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\leq {\tfrac {n-1}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7734394aa5c635df15028412a489a7f48c16fc9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:8.149ex; height:3.676ex;" alt="{\displaystyle v\leq {\tfrac {n-1}{2}}}" loading="lazy"> kleiner oder gleich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {n-1}{2}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {n-1}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3564ea5e9fdceafaa9d5070db79d7ce2278e7dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:3.923ex; height:3.676ex;" alt="{\displaystyle {\tfrac {n-1}{2}}}" loading="lazy">. Dann besitzt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> einen Hamiltonkreis.<a href="#cite_note-SachsI-1">[1]</a></li></ul>

<ul><li><a href="Paul_Erd%C5%91s" title="Paul Erdős">P. Erdős</a> (1962): Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{l}^{n}(k)}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{l}^{n}(k)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3c0f53ad2a58407b2d876c416363c7b1d5453ac6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.066ex; height:3.009ex;" alt="{\displaystyle G_{l}^{n}(k)}" loading="lazy"> ein einfacher Graph mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Knoten und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"> Kanten. Jeder Knoten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{l}^{n}(k)}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{l}^{n}(k)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3c0f53ad2a58407b2d876c416363c7b1d5453ac6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.066ex; height:3.009ex;" alt="{\displaystyle G_{l}^{n}(k)}" loading="lazy"> habe einen Grad <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v(P)\geq k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v(P)\geq k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a8984f42a83d414ad7c7a8f8da4fd4caa21f52b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.992ex; height:2.843ex;" alt="{\displaystyle v(P)\geq k}" loading="lazy">. Es gelte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq k<{\tfrac {n}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq k<{\tfrac {n}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/598f838a4c3638b797cd6c6d578bbee7601a8289.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:10.393ex; height:3.176ex;" alt="{\displaystyle 1\leq k<{\tfrac {n}{2}}}" loading="lazy"> und es sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l(k,n)=1+\max _{k\leq t<{\tfrac {n}{2}}}{\binom {n-t}{2}}+t^{2}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</munder>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l(k,n)=1+\max _{k\leq t<{\tfrac {n}{2}}}{\binom {n-t}{2}}+t^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5f71d1931bfae856d28735dbfbee7acbc6194cf3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:32.691ex; height:7.343ex;" alt="{\displaystyle l(k,n)=1+\max _{k\leq t<{\tfrac {n}{2}}}{\binom {n-t}{2}}+t^{2}}" loading="lazy">. Dann gilt:

<ul><li>1. Jeder Graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{l}^{n}(k)}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{l}^{n}(k)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3c0f53ad2a58407b2d876c416363c7b1d5453ac6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.066ex; height:3.009ex;" alt="{\displaystyle G_{l}^{n}(k)}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l\geq l(k,n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l\geq l(k,n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/35f42a6f90fe18211e9d23e3633af55a09beca6c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.934ex; height:2.843ex;" alt="{\displaystyle l\geq l(k,n)}" loading="lazy"> besitzt einen Hamiltonkreis.</li>

<li>2. Es existiert ein Graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{l(k,n)-1}^{n}(k)}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{l(k,n)-1}^{n}(k)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/04c999add3373be95c6cdbaa42bbd52214fed673.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.505ex; width:11.25ex; height:3.509ex;" alt="{\displaystyle G_{l(k,n)-1}^{n}(k)}" loading="lazy">, der keinen Hamiltonkreis besitzt.<a href="#cite_note-SachsI-1">[1]</a></li></ul></li></ul>

<ul><li><a href="Va%C5%A1ek_Chv%C3%A1tal" title="Vašek Chvátal">V. Chvátal</a> (1972): Ein Tupel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a_{1},\dotsc ,a_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a_{1},\dotsc ,a_{n})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8a2a623d2e6322e07d9afd0b5cf2566ee55722c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.72ex; height:2.843ex;" alt="{\displaystyle (a_{1},\dotsc ,a_{n})}" loading="lazy"> <a href="Nat%C3%BCrliche_Zahl" title="Natürliche Zahl">natürlicher Zahlen</a> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1}\leq \cdots \leq a_{n}<n}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1}\leq \cdots \leq a_{n}<n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e68e84893dc093e96a48d950b1c80776ebd6c9be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.146ex; height:2.343ex;" alt="{\displaystyle a_{1}\leq \cdots \leq a_{n}<n}" loading="lazy"> ist genau dann hamiltonsch, wenn für jedes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i<{\tfrac {n}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i<{\tfrac {n}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c2e154eb73adf6ba0f38bfe833a161ddf27b6640.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:5.723ex; height:3.176ex;" alt="{\displaystyle i<{\tfrac {n}{2}}}" loading="lazy"> gilt: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}\leq i\Rightarrow a_{n-i}\geq n-i}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}\leq i\Rightarrow a_{n-i}\geq n-i}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e731e22090fddefd3aad243b98164cf68bd61f6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:21.975ex; height:2.509ex;" alt="{\displaystyle a_{i}\leq i\Rightarrow a_{n-i}\geq n-i}" loading="lazy">.</li></ul>

<ul><li>V. Chvátal und <a href="Paul_Erd%C5%91s" title="Paul Erdős">P. Erdős</a> (1972): Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> k-<a href="Zusammenh%C3%A4ngender_Graph" class="mw-redirect" title="Zusammenhängender Graph">zusammenhängend</a> und die <a href="M%C3%A4chtigkeit_(Mathematik)" title="Mächtigkeit (Mathematik)">Mächtigkeit</a> jeder Menge unabhängiger Knoten aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \leq k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \leq k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/17f47ca487127f924b3d2025db2eeb1d7ec1dcdc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:3.665ex; height:2.343ex;" alt="{\displaystyle \leq k}" loading="lazy">, so ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> hamiltonsch.</li></ul>

<ul><li><a href="Herbert_Fleischner" title="Herbert Fleischner">H. Fleischner</a> (1974): Ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> 2-zusammenhängend, so hat <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ecc876d9f46199f549440f26bda145d167c76b4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.881ex; height:2.676ex;" alt="{\displaystyle G^{2}}" loading="lazy"> einen Hamiltonkreis.</li></ul>

<ul><li>J. A. Bondy und V. Chvátal (1976): <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> ist genau dann hamiltonsch, wenn sein Hamiltonabschluss hamiltonsch ist.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Weitere_hinreichende_Eigenschaften">Weitere hinreichende Eigenschaften</h3></div>

Ein <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graph</a> ist hamiltonsch, wenn er

<ul><li>ein <a href="Vollst%C3%A4ndiger_Graph" title="Vollständiger Graph">vollständiger Graph</a> mit mindestens drei <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> ist.</li>

<li><a href="Kantengraph" title="Kantengraph">Kantengraph</a> eines <a href="Eulerscher_Graph" class="mw-redirect" title="Eulerscher Graph">Eulerschen</a> oder hamiltonschen Graphen ist.</li>

<li>einen <a href="Teilgraph" title="Teilgraph">Teilgraphen</a>, bei dem nur Kanten entfernt wurden, besitzt, der Kantengraph eines Eulerschen oder hamiltonschen Graphen ist.</li>

<li>ein <a href="Zyklus_(Graphentheorie)#Panzyklischer_Graph" title="Zyklus (Graphentheorie)">panzyklischer Graph</a> ist.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Notwendige_Eigenschaften">Notwendige Eigenschaften</h3></div>

Hat ein <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graph</a> einen Hamiltonkreis, dann

<ul><li>hat er keinen <a href="Schnittknoten" class="mw-redirect" title="Schnittknoten">Schnittknoten</a>.</li>

<li>hat er keine <a href="Trenner_(Graphentheorie)" title="Trenner (Graphentheorie)">Brücke</a>.</li>

<li>ist sein <a href="Blockgraph" title="Blockgraph">Blockgraph</a> ein <a href="Knoten_(Graphentheorie)#Spezielle_Knoten" title="Knoten (Graphentheorie)">isolierter Knoten</a>.</li>

<li>hat er einen 2-<a href="Faktor_(Graphentheorie)" title="Faktor (Graphentheorie)">Faktor</a>.</li>

<li>ist er 2-<a href="Zusammenh%C3%A4ngender_Graph" class="mw-redirect" title="Zusammenhängender Graph">zusammenhängend</a>.</li>

<li>ist sein <a href="Minimalgrad" class="mw-redirect" title="Minimalgrad">Minimalgrad</a> mindestens 2.</li>

<li>ist sein <a href="Durchmesser_(Graphentheorie)" class="mw-redirect" title="Durchmesser (Graphentheorie)">Durchmesser</a> höchstens <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {n}{2}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {n}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c2fd493036e5cdcb87f9ddfdc7ab475e74636b5e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:1.822ex; height:3.176ex;" alt="{\displaystyle {\tfrac {n}{2}}}" loading="lazy">.</li>

<li>ist er 1-tough, d. h. für jede nicht-leere Menge von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> gilt, dass der <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graph</a> ohne diese Knoten höchstens <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> Zusammenhangskomponenten besitzt.</li>

<li>ist path-tough, d. h. für jeden Knoten gilt, dass der Graph ohne diesen Knoten einen Hamiltonschen Weg besitzt, das ist ein Weg, der alle Knoten des Graphen enthält.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Vermutungen">Vermutungen</h3></div>

In diesem Zusammenhang wurden diese wichtigen – nicht allgemein gelösten – <a href="Vermutung_(Mathematik)" title="Vermutung (Mathematik)">Vermutungen</a> geäußert:

<ul><li>D. W. Barnette (1969): Jeder 3-zusammenhängende <a href="Bipartiter_Graph" title="Bipartiter Graph">bipartite</a> <a href="Kubischer_Graph" title="Kubischer Graph">kubische</a> planare Graph ist hamiltonsch.</li></ul>

<ul><li><a href="Paul_Seymour_(Mathematiker)" title="Paul Seymour (Mathematiker)">P. Seymour</a> (1974): Ist der Minimalgrad von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta (G)\geq {\tfrac {k}{k+1}}n}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta (G)\geq {\tfrac {k}{k+1}}n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ff28d8ed00a7edd4f27aa693403fb574d0400e05.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:12.971ex; height:3.843ex;" alt="{\displaystyle \delta (G)\geq {\tfrac {k}{k+1}}n}" loading="lazy">, so hat <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> einen Hamiltonkreis <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H^{k}\subseteq G}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H^{k}\subseteq G}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/07a99fff8c03f89733bf97cdf354b3c5df7a7cd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.117ex; height:2.843ex;" alt="{\displaystyle H^{k}\subseteq G}" loading="lazy">. Für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6c035ffa69b5bca8bf2d16c3da3aaad79a8bcbfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=1}" loading="lazy"> entspricht dies dem Satz von G. A. Dirac, 1952, (siehe oben). Die Aussage für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0bd301789e1f25a3da4be297ff637754ebee5f5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=2}" loading="lazy"> war bereits 1963 von L. Pósa vermutet worden und wurde 1996 für hinreichend große <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> von J. Komlós, G. N. Sárközy & <a href="Endre_Szemer%C3%A9di" title="Endre Szemerédi">E. Szemerédi</a> bewiesen.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li>Ein Spezialfall des Hamiltonkreises ist das sogenannte <a href="Springerproblem" title="Springerproblem">Springerproblem</a>.</li>

<li>Die <a href="Gray-Code" title="Gray-Code">Gray-Codes</a> sind die Lösungen des Hamiltonkreisproblems für einen Hyperwürfel.</li>

<li><a href="Selbstmeidender_Pfad" title="Selbstmeidender Pfad">Selbstmeidender Pfad</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noresize noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"></div><a class="external text" href="https://commons.wikimedia.org/wiki/Category:Hamiltonian_paths?uselang=de">Commons: Hamiltonian paths</a> – Sammlung von Bildern, Videos und Audiodateien</div>

<ul><li><a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/HamiltonianCycle.html">Eric W. Weisstein. „Hamiltonian Cycle.“ From MathWorld--A Wolfram Web Resource</a> (englisch)</li>

<li><a rel="nofollow" class="external text" href="https://www.puzzlemuseum.com/month/picm02/200207icosian.htm">Puzzlemuseum: Hamiltons Spiele „The Icosian Game“ und „Traveller's Dodecahedron“</a> (englisch)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<a href="Horst_Sachs" title="Horst Sachs">Horst Sachs</a>: <cite style="font-style:italic">Einführung in die Theorie der endlichen Graphen (Band 1)</cite>. 1. Auflage. BSB B.G. Teubner Verlagsgesellschaft, Leipzig 1970.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Hamiltonkreisproblem&rft.au=Horst+Sachs&rft.btitle=Einf%C3%BChrung+in+die+Theorie+der+endlichen+Graphen+%28Band+1%29&rft.date=1970&rft.edition=1.&rft.genre=book&rft.place=Leipzig&rft.pub=BSB+B.G.+Teubner+Verlagsgesellschaft" style="display:none">

</li>

</ol>

/* start https://de.wikipedia.org/ */

.mw-parser-output div.klappleiste{border:1px solid var(--dewiki-rahmenfarbe1);clear:both;font-size:95%;box-sizing:border-box;margin-top:1.5em;padding:2px}.mw-parser-output div.klappleiste:after{clear:both;content:"";display:block}.mw-parser-output div.klappleiste-bild{float:left;padding:2px}.mw-parser-output div.klappleiste-kopf{background:var(--dewiki-hintergrundfarbe5);color:var(--color-base,#202122);text-align:center;font-weight:bold}.mw-parser-output div.klappleiste.mw-collapsed .klappleiste-bild{display:none}.mw-parser-output div.klappleiste+div.klappleiste,.mw-parser-output div.klappleiste+link+div.klappleiste,.mw-parser-output div.klappleiste+link+link+div.klappleiste,.mw-parser-output div.klappleiste+link+style+div.klappleiste,.mw-parser-output div.klappleiste+style+div.klappleiste,.mw-parser-output div.klappleiste+style+style+div.klappleiste,.mw-parser-output div.klappleiste+style+link+div.klappleiste{margin-top:-1px}@media screen{html.skin-theme-clientpref-night .mw-parser-output .klappleiste-bild span[typeof="mw:File"]:not(.skin-invert-image) img{background-color:#c8ccd1}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .klappleiste-bild span[typeof="mw:File"]:not(.skin-invert-image) img{background-color:#c8ccd1}}

/* end https://de.wikipedia.org/ */

</style>

<div class="klappleiste-kopf"><a href="Karps_21_NP-vollst%C3%A4ndige_Probleme" title="Karps 21 NP-vollständige Probleme">Karps 21 NP-vollständige Probleme</a></div>

<a href="Erf%C3%BCllbarkeitsproblem_der_Aussagenlogik" title="Erfüllbarkeitsproblem der Aussagenlogik">Erfüllbarkeitsproblem der Aussagenlogik</a> |

<a href="Cliquenproblem" title="Cliquenproblem">Cliquenproblem</a> |

<a href="Mengenpackungsproblem" title="Mengenpackungsproblem">Mengenpackungsproblem</a> |

<a href="Knoten%C3%BCberdeckungsproblem" class="mw-redirect" title="Knotenüberdeckungsproblem">Knotenüberdeckungsproblem</a> |

<a href="Mengen%C3%BCberdeckungsproblem" title="Mengenüberdeckungsproblem">Mengenüberdeckungsproblem</a> |

<a href="Feedback_Arc_Set" title="Feedback Arc Set">Feedback Arc Set</a> |

<a href="Feedback_Vertex_Set" title="Feedback Vertex Set">Feedback Vertex Set</a> |

<a class="mw-selflink selflink">Hamiltonkreisproblem</a> |

<a href="Ganzzahlige_lineare_Optimierung#0.2F1-Programmierung" title="Ganzzahlige lineare Optimierung">Integer Linear Programming</a> |

<a href="3-SAT" title="3-SAT">3-SAT</a> |

<a href="F%C3%A4rbung_(Graphentheorie)" title="Färbung (Graphentheorie)">graph coloring problem</a> |

Covering by cliques |

<a href="Problem_der_exakten_%C3%9Cberdeckung" title="Problem der exakten Überdeckung">Problem der exakten Überdeckung</a> |

3-dimensional matching |

<a href="Steinerbaumproblem" title="Steinerbaumproblem">Steinerbaumproblem</a> |

<a href="Hitting-Set-Problem" title="Hitting-Set-Problem">Hitting set</a> |

<a href="Rucksackproblem" title="Rucksackproblem">Rucksackproblem</a> |

Job sequencing |

<a href="Partitionsproblem" title="Partitionsproblem">Partitionsproblem</a> |

<a href="Maximaler_Schnitt" title="Maximaler Schnitt">Maximaler Schnitt</a>

</div></div>

<div>

Normdaten (Sachbegriff): <a href="Gemeinsame_Normdatei" title="Gemeinsame Normdatei">GND</a>: <a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4504638-4">4504638-4</a> </div>

</div></div></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-02-04" href="https://de.wikipedia.org/wiki/?title=Hamiltonkreisproblem&oldid=252976545">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>